#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        if (n == 1 && gas[0] >= cost[0])
            return 0;
        vector<int> dif(n);
        for (int i = 0; i < n; ++i)  dif[i] = gas[i] - cost[i];

        for (int i = 0; i < n;)
        {
            if (dif[i] >= 0)
            {
                int count = dif[i];
                int j = 0;
                for (j = (i + 1) % n;;)
                {
                    count += dif[j];
                    if (count < 0)
                        break;
                    if (j == i)
                        return i;
                    j = (j + 1) % n;
                }
                if (j + 1 <= i)
                    break;
                else
                    i = j + 1;
            }
            else
                i++;
        }

        return -1;
    }
};